Several queries and scores have recently been proposed to explain individual predictions over ML models. Examples include queries based on "anchors", which are parts of an instance that are sufficient to justify its classification, and "feature-perturbation" scores such as SHAP. Given the need for flexible, reliable, and easy-to-apply interpretability methods for ML models, we foresee the need for developing declarative languages to naturally specify different explainability queries. We do this in a principled way by rooting such a language in a logic called FOIL, which allows for expressing many simple but important explainability queries, and might serve as a core for more expressive interpretability languages. We study the computational complexity of FOIL queries over two classes of ML models often deemed to be easily interpretable: decision trees and more general decision diagrams. Since the number of possible inputs for an ML model is exponential in its dimension, tractability of the FOIL evaluation problem is delicate but can be achieved by either restricting the structure of the models, or the fragment of FOIL being evaluated. We also present a prototype implementation of FOIL wrapped in a high-level declarative language and perform experiments showing that such a language can be used in practice.

Large Language Models (LLMs) still struggle with complex logical reasoning. While previous works achieve remarkable improvements, their performance is highly dependent on the correctness of translating natural language (NL) problems into a symbolic language (SL). Though numerous works focusing on improving this translation accuracy, they only consider the similarity between the meaning of SL and NL, overlooking another crucial influencing factor, the selection of the target SL type itself. For example, first-order logic language specializes in logical reasoning with categorical syllogisms and complex quantifiers, while Boolean satisfiability formalism excels at representing constraint satisfaction like partial problems. To our knowledge, this is the first paper to claim and verify that different NL logical reasoning problem corresponds to different optimal SL formalization for translation. Based on this, we propose a methods to improve the logical reasoning performance of LLMs by adaptively selecting the most suitable SL for each problem prior to translation. Specifically, we leverage LLMs to select the target SL among first-order logic, logic programming and Boolean satisfiability and then translate the problem in NL to target SL expressions as well as employ the corresponding logical solver to derive the final answer. Experimental results on benchmarks show that our adaptive selection method significantly outperforms translating all into single SL and randomly selecting the SL. On a mixed dataset of these benchmarks, our approach achieves 96% accuracy, which improving performance by 25% compared to the second highest accuracy from the first-order logic translation.

Advances in artificial intelligence (AI), particularly large language models (LLMs) [1], have achieved remarkable success. This progress stems from "scaling laws" -- performance improves with greater computation, data, and model size [2]. They now excel at mathematics, medical, legal, and coding exams and competitions. Y et, this paradigm has a crucial vulnerability: scaling laws are effective only when data is abundant. Human reasoning, which relies on logical operations and abstractions rather than brute-force pattern matching on vast data, proves critical in tackling complex frontier domains, where usable data is often inherently scarce.

Several queries and scores have recently been proposed to explain individual predictions over ML models. Examples include queries based on "anchors", which are parts of an instance that are sufficient to justify its classification, and "feature-perturbation" scores such as SHAP. Given the need for flexible, reliable, and easy-to-apply interpretability methods for ML models, we foresee the need for developing declarative languages to naturally specify different explainability queries. We do this in a principled way by rooting such a language in a logic called FOIL, which allows for expressing many simple but important explainability queries, and might serve as a core for more expressive interpretability languages. We study the computational complexity of FOIL queries over two classes of ML models often deemed to be easily interpretable: decision trees and more general decision diagrams.

The recent development of formal explainable AI has disputed the folklore claim that "decision trees are readily interpretable models", showing different interpretability queries that are computationally hard on decision trees, as well as proposing different methods to deal with them in practice. Nonetheless, no single explainability query or score works as a "silver bullet" that is appropriate for every context and end-user. This naturally suggests the possibility of "interpretability languages" in which a wide variety of queries can be expressed, giving control to the end-user to tailor queries to their particular needs. In this context, our work presents ExplainDT, a symbolic language for interpreting decision trees. ExplainDT is rooted in a carefully constructed fragment of first-ordered logic that we call StratiFOILed. StratiFOILed balances expressiveness and complexity of evaluation, allowing for the computation of many post-hoc explanations--both local (e.g., abductive and contrastive explanations) and global ones (e.g., feature relevancy)--while remaining in the Boolean Hierarchy over NP. Furthermore, StratiFOILed queries can be written as a Boolean combination of NP-problems, thus allowing us to evaluate them in practice with a constant number of calls to a SAT solver. On the theoretical side, our main contribution is an in-depth analysis of the expressiveness and complexity of StratiFOILed, while on the practical side, we provide an optimized implementation for encoding StratiFOILed queries as propositional formulas, together with an experimental study on its efficiency.

Hanson: OK Geoff, thanks for joining me in this chat. This is for AIhub, and I've recorded three or four different conversations and it sort of started out thinking about– what is AI, but it really started out with an old friend of mine (we overlapped in Graduate School), Michael Jordan, who had written several articles (one in Medium) and I wrote a reply, which got some attention, mainly from Mike. He and I had this discussion and I disagreed so much with him I wanted to just see what was going on. Even if you haven't been paying attention you'll notice that something is happening. He was basically saying that the deep-learning phenomenon that's happening right now is – I almost think of it as like The Beatles, when Beatlemania started, we're in deep-learning mania. But, there's a lot of good things happening too, and as I pointed out to him, protein folding.. He said "I agree, but of course, they didn't solve the problem!". I said "you're creating these diminishing comments to create an atmosphere of'this is going to fail, the AI winter is going to come'. Why are you doing this? Don't you realize you're like the only person who doesn't get this". Hanson: Now I know that because I've debated him back in the 80s!, I will warn you this is a Gary Marcus free zone and I'm not going to talk about him. Hinton: In 2015 he made a prediction that computers wouldn't be able to do machine translation. Hanson: Yes, I know, but Gary is the most inconsistent… consistently inconsistent person I know. I wish people would stop taking him so seriously. Anyway, I knew Michael back in grad school and at that point he was always focused on the margins of things – I mean, important things. There's a sense in which he really is rejecting the whole DL thing strongly, and he's an interesting character in this. Now, you on the other hand have had, at least what I've heard you say in other contexts, that deep learning concerns you. I think that Yoshua Bengio has had a lot of concerns as well about DL. So we're doing classification and it works well, but how does it compare to human thought and reasoning, and all the wonderful things humans do?

I was electrified by Jonathan Berger's music before I knew he wrote about music. His chamber works arise out of a lightning storm of modernist angles, dramatic and startling, though anchored to melodies that sail like a swallow, as one of his string quartets is called. His one-act operas Theotokia and The War Reporter, performed together in concert, match taut musical brocades to the hallucinations of, respectively, a schizophrenic, hearing voices of various mothers, and a photojournalist, based on Paul Watson, who won the 1994 Pulitzer Prize for his image of the corpse of an American soldier being dragged through the streets of Mogadishu. A few years ago, I read some of Jonathan's academic writing about music, which had a sharp focus on neurology and acoustics. He is a professor of music at Stanford, where he teaches composition, music theory, and cognition at the Center for Computer Research in Music and Acoustics. On a hunch that he could connect with a popular audience, I asked him to write an essay for Nautilus about how composers upend expectations to keep listeners off guard and engaged. That article, "Composing Your Thoughts," and his next one for Nautilus, "How Music Hijacks Our Perception of Time," which contain musical clips to illustrate his points, have been among our most popular articles. There's a certain amount of problem solving that happens in the context of a band of noise. For this month's issue I called Jonathan and was delighted to learn he had thought a lot about noise.